#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "queue"
using namespace std;
/*HJJ QQ479287006
 *todo 层序遍历BFS一般都是需要用队列来辅助实现，不同于深度优先DFS，BFS一般是不用递归的。递归会导致越来越深入，不符合广度优先

  要求队列和深度遍历两种实现方法
 * */

//字节 面试 使用递归实现 层次遍历 返回Vector
vector<vector<int>> levelOrder(TreeNode* root) {

    vector<vector<int>> ret;

    if(root==nullptr){
        return ret;
    }


    queue<TreeNode*> q;

    q.push(root);

    while(!q.empty()){

        int sizer=q.size();


        vector<int> t;
        for(int i=0;i<sizer;i++){
            TreeNode* temp=q.front();
            q.pop();
            if(temp->left){
                q.push(temp->left);
            }if(temp->right){

                q.push(temp->right);
            }

            t.push_back(temp->val);
        }
        ret.push_back(t);
    }


    return ret;

}



//字节 面试 使用递归实现 层次遍历 返回Vector
vector<vector<int>> ret;

void levelOrder_r(TreeNode* root,int depth) {
    if (root== nullptr)
        return;
    if (ret.size()==depth) ret.push_back(vector<int>());


    ret[depth].push_back(root->val);
    levelOrder_r(root->left,depth+1);
    levelOrder_r(root->right,depth+1);

}

vector<vector<int>> levelOrder(TreeNode* root) {


    levelOrder_r(root,0);


    return ret;

}